package com.leetcode.problems030;


import java.util.*;

/**
 * https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {


    public List<Integer> findSubstring(String s, String[] words) {
        //每个单词的长度
        int len = words[0].length();
        int allLen = len * words.length;
        List<Integer> res = new ArrayList<>();
        HashMap<String,Integer> wordMaps = buildWordMaps(words);
        for(int i = 0; i + allLen <= s.length(); i++){
            boolean flag = findSubstring(s,len,i,wordMaps);
            if(flag){res.add(i);}
        }
        return res;
    }

    private HashMap<String, Integer> buildWordMaps(String[] words) {
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            Integer wCount = map.getOrDefault(words[i],0);
            map.put(words[i],wCount + 1);
        }
        return map;
    }

    public boolean findSubstring(String s, int len,int startIndex, HashMap<String,Integer> wordMaps) {
        if(wordMaps.size() == 0){
            return true;
        }
        if(startIndex + len > s.length()){
            return false;
        }
        String curStr = s.substring(startIndex,startIndex + len);
        Integer wCount = wordMaps.getOrDefault(curStr,0);
        if(wCount == 0){
            return false;
        }
        if(wCount - 1 == 0){
            wordMaps.remove(curStr);
        }else{
            wordMaps.put(curStr,wCount - 1);
        }
        boolean flag = findSubstring(s,len,startIndex + len,wordMaps);
        wordMaps.put(curStr,wCount);
        return  flag;
    }


    public static void main(String[] args) {
        String s = "wordgoodgoodgoodbestword";
        String[] words = {"word","good"};
        System.out.println(new Solution().findSubstring(s,words));
    }
}
